package com.tianyuan.test1;
import java.util.*;
/**递归/回溯 */
/**
 * 没有重复项数字的全排列
 *  //  TODO
 * @date 2025/10/19 11:14
 * 给出一组数字，返回该组数字的所有排列
 * 例如：
 * [1,2,3]的所有排列如下
 * [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]
 * （以数字在数组中的位置靠前为优先级，按字典序排列输出。）
 * 数据范围:数字个数0<n≤6
 *
 * 输入：[1,2,3]   返回值：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 输入：[1]   返回值：[[1]]
 */
public class Solution {
    /**
     * 求数组的全排列（所有可能的元素排列组合）
     * 例如输入[1,2]，输出[[1,2],[2,1]]
     */
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // 用来存所有排列结果的大列表
        ArrayList<ArrayList<Integer>> allPermutations = new ArrayList<>();
        // 启动递归，开始拼第一个排列
        // 参数：原数组、结果列表、当前正在拼的排列（临时列表）
        backtrack(num, allPermutations, new ArrayList<>());
        return allPermutations;
    }
    /**
     * 回溯核心方法：负责一步步拼出排列，拼完一种就记录，然后退回上一步试其他可能
     * @param num 原数组（所有可选的数字）
     * @param result 最终要返回的所有排列
     * @param current 当前正在拼的排列（比如拼到一半的[1,3]）
     */
    void backtrack(int[] num, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> current) {
        // 终止条件：如果当前拼的排列长度和原数组一样，说明拼完了一种
        if (current.size() == num.length) {
            // 把当前排列的副本存进结果（不能直接存current，因为后面还要修改它）
            result.add(new ArrayList<>(current));
            return; // 结束当前递归，回到上一步
        }
        // 遍历原数组，尝试往当前排列里加一个没加过的数
        for (int i = 0; i < num.length; i++) {
            int currentNum = num[i];
            // 如果这个数已经在当前排列里了，就跳过（避免重复用同一个数，比如[1,1]）
            if (current.contains(currentNum)) {
                continue;
            }
            // 1. 选数：把当前数加入正在拼的排列
            current.add(currentNum);
            // 2. 递归：继续拼下一个位置（比如当前是[1]，递归后会尝试加2或3）
            backtrack(num, result, current);
            // 3. 回溯：把刚加的数删掉，回到上一步（比如拼完[1,2,3]后，删掉3回到[1,2]，再试其他数）
            current.remove(current.size() - 1);
        }
    }





    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例1：[1,2,3]
        int[] num1 = {1, 2, 3};
        System.out.println("输入：[1,2,3]");
        System.out.println("全排列结果：" + solution.permute(num1) + "\n");

        // 测试用例2：[1]
        int[] num2 = {1};
        System.out.println("输入：[1]");
        System.out.println("全排列结果：" + solution.permute(num2));
    }
}
